package com.leetcode.专项突破.二叉树;

import com.leetcode.common.model.TreeNode;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

/**
 * @author 覃国强
 * @date 2022-04-10 15:11
 */
public class InorderTraversal {


  static
  class Solution {

    public List<Integer> inorderTraversal(TreeNode root) {
//      List<Integer> answers = new ArrayList<>();
//      inorderTraversalWithRecursion(root, answers);
//      return answers;
      return inorderTraversalWithStack(root);
    }

    private void inorderTraversalWithRecursion(TreeNode root, List<Integer> answers) {
      if (root == null) {
        return;
      }
      inorderTraversalWithRecursion(root.left, answers);
      answers.add(root.val);
      inorderTraversalWithRecursion(root.right, answers);
    }

    private List<Integer> inorderTraversalWithStack(TreeNode root) {
      List<Integer> answers = new ArrayList<>();
      if (root == null) {
        return answers;
      }
      Deque<TreeNode> stack = new ArrayDeque<>();
      while (root != null || !stack.isEmpty()) {
        if (root != null) {
          stack.push(root);
          root = root.left;
        } else {
          root = stack.pop();
          answers.add(root.val);
          root = root.right;
        }
      }
      return answers;
    }

  }

}
